package org.example;

public class Test2 {
    //leetcode 222 完全二叉树的结点个数 https://leetcode.cn/problems/symmetric-tree/description/

    /**
     * 将完全二叉树当成普通二叉树看待
     * @param root
     * @return
     */
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int leftNum = countNodes(root.left);
        int rightNum = countNodes(root.right);
        return leftNum + rightNum + 1;
    }

    /**
     * 按照完全二叉树的方式做
     * @param root
     * @return
     */
    public int countNodes2(TreeNode root) {
        if (root == null) return 0;
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftNum = 0, rightNum = 0;
        while (left != null) {
            leftNum++;
            left = left.left;
        }
        while (right != null) {
            rightNum++;
            right = right.right;
        }
        //leftNum = rightNum的时候就说明此时以root为根节点的树为完全二叉树
        if (leftNum == rightNum) return (2 << leftNum) - 1;
        return countNodes2(root.left) + countNodes2(root.right) + 1;
    }
}
